package main.图;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author tmh
 * @date 2024/7/25 11:01
 * @description 这道题应该算是图的广度遍历
 */
public class T994腐烂的橘子 {
    /**
     * 预备知识：(i,j)位置的元素可以存成i*n+j=m，还原的时候，就直接m/n,m%n;n是数组的列的长度
     *
     * @param grid
     * @return
     */
    public int orangesRotting(int[][] grid) {
        //使用direction来往四个方向遍历
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        //定义totalOrange统计所有橘子个数
        int totalOrange = 0;
        //定义一个队列来进行BFS操作，队列里面保存的是所有腐烂的橘子的位置
        Deque<Integer> deque = new ArrayDeque<>();
        int m = grid.length;
        int n = grid[0].length;
        //统计所有橘子的个数，并且将初始腐烂橘子的坐标id（id为经过横纵坐标计算之后得到的值）加入队列里面，方便存储
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    totalOrange++;
                    if (grid[i][j] == 2) {
                        deque.offer(i * n + j);
                    }
                }
            }
        }
        //判断初始化两个情况：
        //1.腐烂橘子为空（队列为空），总的橘子也为空，即就是没有新鲜橘子，返回0
        //2.腐烂橘子为空，总的橘子不为空，即就是有新鲜橘子，没有腐烂橘子，返回-1
        if (deque.isEmpty()) {
            return totalOrange == 0 ? 0 : -1;
        }
        //统计最终腐烂的橘子数
        //统计时间：初始化为-1
        int rotOrange = 0;
        int minutes = -1;
        //开始广度遍历
        while (!deque.isEmpty()) {
            int len = deque.size();
            //累计的腐烂橘子个数
            rotOrange += len;
            minutes++;
            while (len > 0) {
                Integer id = deque.poll();
                //根据id还原腐烂橘子的横纵坐标
                int row = id / n;
                int col = id % n;
                //开始往四个方向遍历
                for (int[] direction : directions) {
                    int nr = row + direction[0];
                    int nc = col + direction[1];
                    // 坐标合法且为新鲜橘子，则被扩散为腐烂
                    if (isArea(grid, nr, nc) && grid[nr][nc] == 1) {
                        //将新鲜橘子标记为腐烂
                        grid[nr][nc] = 2;
                        //将新腐烂的橘子坐标id加入到队列里面
                        deque.offer(nr * n + nc);
                    }
                }
                len--;
            }
        }
        // 如果最终腐烂的橘子数等于总橘子数，则有解；否则无解返回-1
        return rotOrange == totalOrange ? minutes : -1;

    }

    private boolean isArea(int[][] grid, int row, int col) {
        return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length;
    }
}
